|
In automata theory, McNaughton's theorem refers to a theorem that asserts that the set of ω-regular languages is identical to the set of languages recognizable by deterministic Muller automata. 〔McNaughton, R.: "Testing and generating infinite sequences by a finite automaton", ''Information and control 9'', pp. 521–530, 1966.〕 This theorem is proven by supplying an algorithm to construct a deterministic Muller automaton for any ω-regular language and vice versa. This theorem has many important consequences. Since Büchi automata and ω-regular languages are equally expressive, the theorem implies that Büchi automata and deterministic Muller automata are equally expressive. Since complementation of deterministic Muller automata is trivial, the theorem implies that Büchi automata/ω-regular languages are closed under complementation. ==Original statement== In McNaughton's original paper, the theorem was stated as: "An ω-event is regular if and only if it is finite-state." In modern terminology, ''ω-events'' are commonly referred to as ω-languages. Following McNaughton's definition, an ω-event is a ''finite-state event'' if there exists a deterministic Muller automaton that recognizes it. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「McNaughton's theorem」の詳細全文を読む スポンサード リンク
|